package recursion;

/**
 * 递归实现插入排序
 *
 * @author yyz
 * @create 2023-11-12 13:58
 */
public class InsertionSort {
    public static void sort(int[] a) {
        f(a, 1, a.length - 1);
    }

    /**
     * 插入排序函数
     * @param a 待排序的数组
     * @param low 边界
     */
    private static void f(int[] a, int low) {
        if (low > a.length - 1) {
            return;
        }

        int t = a[low];
        int i = low - 1;

        while (i >= 0 && a[i] > t) {
            a[i + 1] = a[i];
            i--;
        }

        if (i + 1 != low) {
            a[i + 1] = t;
        }

        f(a, low + 1);
    }

    private static void f(int[] a, int low, int high) {
        if (low > high) {
            return;
        }

        int i = low - 1;
        int t = a[low];

        while (i >= 0 && a[i] > t) {
            a[i + 1] = a[i];
            i--;
        }
        if (i + 1 != low) {
            a[i + 1] = t;
        }
        f(a, low + 1, high);
    }
}
